/**
 *
 */
package leetCode;

import java.util.*;

/**
 * @author zhongfang
 */
public class threeSum {
    /**
     * 瓒呮椂
     * 鎺掑簭
     * O(N*N*N)
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        Set<String> set = new HashSet<>();
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int target = 0 - (nums[i] + nums[j]);
            if (target < nums[i]) {
                j--;
            } else if (target > nums[j]) {
                i++;
            } else {
                for (int k = i + 1; k < j; k++) {
                    if (nums[k] == target) {
                        if (set.add("" + nums[i] + nums[k] + nums[j])) {
                            ArrayList<Integer> list = new ArrayList<>(3);
                            list.add(nums[i]);
                            list.add(nums[k]);
                            list.add(nums[j]);
                            res.add(list);
                        }
                    }
                }
            }
        }
        return res;
    }


    /**
     * 瓒呮椂
     * hash
     * O(N*N)
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum3(int[] nums) {
        Arrays.sort(nums);
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int sum = nums[i] + nums[j];
                if (!map.containsKey(sum)) {
                    map.put(sum, new ArrayList<>());
                }
                map.get(sum).add(i);
                map.get(sum).add(j);
            }
        }
        List<List<Integer>> res = new ArrayList<>();
        Set<String> dup = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if (map.containsKey(0 - nums[i])) {
                List<Integer> list = map.get(0 - nums[i]);
                for (int j = 0; j < list.size(); j += 2) {
                    int a = list.get(j);
                    int b = list.get(j + 1);
                    if (a != i && b != i) {//鍙互鏀惧叆缁撴灉锛屼絾鏄渶瑕佹牴鎹�煎幓閲�
                        if (dup.add(getStr(nums[i], nums[a], nums[b]))) {
                            List<Integer> list1 = new ArrayList<>();
                            list1.add(nums[i]);
                            list1.add(nums[a]);
                            list1.add(nums[b]);
                            res.add(list1);
                        }
                        while (b + 1 < nums.length && j < list.size() - 2 && nums[b + 1] == nums[a]) {
                            j += 2;
                            a = list.get(j);
                            b = list.get(j + 1);
                        }
                    }
                }
            }
        }

        return res;
    }

    private String getStr(int num, int num1, int num2) {
        int[] a = {num, num2, num1};
        Arrays.sort(a);
        return a[0] + "_" + a[1] + "_" + a[2];
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int target = 0 - nums[i];
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                int sum = nums[j] + nums[k];
                if (sum == target) {
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));

                    while (j < k && nums[j] == nums[j + 1]) j++;
                    while (j < k && nums[k] == nums[k - 1]) k--;
                    j++;//涓�瀹氳鏀惧埌while鍚庨潰锛侊紒锛�
                    k--;
                } else if (sum > target) {
                    k--;
                } else {
                    j++;
                }
            }
        }
        return res;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> res = new threeSum().threeSum(nums);
    }

}
